package com.lenl.arithmetic.sort;

import java.util.Arrays;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-02 10:30
 * @description 快速排序，无限二分
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr={-9,78,0,23,-567,70,0,-8,-567};
        doQuickSort(arr,0,arr.length-1);

        System.out.println(Arrays.toString(arr));
    }

    public static void doQuickSort(int[] arr,int left,int right){
        int l=left;//左下标
        int r=right;//右下标
        //pivot中轴值
        int pivot=arr[(left+right)/2];
        //交换时使用
        int temp=0;
        //while循环的目的是让比pivot小的值放在左边，大的放右边
        while(l<r){
            //在pivot的左边一直找
            while(arr[l]<pivot){
                l+=1;
            }
            //在pivot右边一直找
            while (arr[r]>pivot){
                r-=1;
            }
            //如果l>=r，说明pivot左右两边的值已经移完
            if(l>=r){
                break;
            }
            //交换
            temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;

            //防止arr[l]与arr[r]相等，做无谓的交换。
            //如果交换完，arr[l]==pivot，r前移
            if(arr[l]==pivot)
                r-=1;
            //如果arr[r]==pivot,l后移
            if(arr[r]==pivot){
                l+=1;
            }
        }

        //如果l==r，必须错开，否则出现栈溢出
        if(l==r){
            l+=1;
            r-=1;
        }
        //向左递归
        if(left<r){
            doQuickSort(arr,left,r);
        }
        //向右递归
        if(right>l){
            doQuickSort(arr,l,right);
        }

    }

}
